package com.company.other;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 144. 二叉树的前序遍历
 * 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
 * 示例 1：
 *
 *
 * 输入：root = [1,null,2,3]
 * 输出：[1,2,3]
 * 示例 2：
 *
 * 输入：root = []
 * 输出：[]
 * 示例 3：
 *
 * 输入：root = [1]
 * 输出：[1]
 * 示例 4：
 *
 *
 * 输入：root = [1,2]
 * 输出：[1,2]
 * 示例 5：
 *
 *
 * 输入：root = [1,null,2]
 * 输出：[1,2]
 * 提示：
 *
 * 树中节点数目在范围 [0, 100] 内
 * -100 <= Node.val <= 100
 * */
public class PreorderTraversal {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    /**
     * 方法：栈非递归遍历
     * 步骤：
     *      1.从根节点开始，访问根节点，遍历到左孩子，按照此方法依次入栈所有左孩子，直到左孩子为空。执行2
     *      2.出栈栈顶节点，遍历到右孩子，如果右孩子为空，执行2,没有则执行1。
     *      ...
     * */
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer>  res = new ArrayList<>();
        TreeNode node = root;
        while(node != null || !stack.isEmpty()){
            if(node != null){
                res.add(node.val);
                stack.push(node);
                node = node.left;
            }else{
                node = stack.pop().right;
            }
        }
        return res;
    }
}
